package com.fjl.second;

public class BinarySearch {

    /*
    2.二分查找
     给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
     示例 1:
         输入: nums = [-1,0,3,5,9,12], target = 9
         输出: 4
         解释: 9 出现在 nums 中并且下标为 4

     示例 2:
         输入: nums = [-1,0,3,5,9,12], target = 2
         输出: -1
         解释: 2 不存在 nums 中因此返回 -1
     提示：
     1. 你可以假设 nums 中的所有元素是不重复的。
     2. n 将在 [1, 10000]之间。
     3. nums 的每个元素都将在 [-9999, 9999]之间。
     */
    public int search(int[] nums, int target) {
        // 避免当 target 小于nums[0] nums[nums.length - 1]时多次循环运算
        if (target < nums[0] || target > nums[nums.length - 1]) {
            return -1;
        }
        int left = 0;
        int right = nums.length - 1; // [left, right]左闭右闭区间
        while (left <= right) { // 那么这里就应该用=号,因为left==right时,在[left, right]是有意义的
            int mid = (right + left) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (target < nums[mid]) {
                right = mid - 1; //因为当前这个nums[middle]一定不是target，那么接下来要查找的左区间结束下标位置就是 middle - 1
            } else {
                left = mid + 1;
            }
        }
        return -1;
    }

    public static int search1(int[] nums, int target) {
        // 避免当 target 小于nums[0] nums[nums.length - 1]时多次循环运算
        if (target < nums[0] || target > nums[nums.length - 1]) {
            return -1;
        }
        int left = 0;
        int right = nums.length; // [left, right)左闭右闭区间
        while (left < right) { // 那么这里就不应该用=号,因为left==right时,在[left, right)是没有意义的
            int mid = (right + left) >> 1;
            if (nums[mid] == target) {
                return mid;
            } else if (target < nums[mid]) {
                right = mid; //因为当前这个nums[middle]一定不是target，那么接下来要查找的左区间结束下标位置就是 middle,保持[left, right)一致
            } else {
                left = mid + 1;
            }
        }
        return -1;
    }

    // 寻找左侧边界的二分搜索
    public static int left_bound(int[] nums, int target) {
        // 避免当 target 小于nums[0] nums[nums.length - 1]时多次循环运算
        if (target < nums[0] || target > nums[nums.length - 1]) {
            return -1;
        }
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                // 收缩右侧边界
                right = mid - 1;
            } else if (target < nums[mid]) {
                // 搜索区间变为 [left, mid-1]
                right = mid - 1;
            } else if (target > nums[mid]) {
                left = mid + 1;
            }
        }
//        return left;
        /*
        直接return left。如果 target 不存在，搜索左侧边界的二分搜索返回的索引是大于 target 的最小索引。
        举个例子，nums = [2,3,5,7], target = 4，left_bound 函数返回值是 2，因为元素 5 是大于 4 的最小元素。
        为什么呢？因为当最后一次循环时，left=right,然后有两个分支是right = mid - 1;一个分支是left = mid + 1;
        那么必然最后一次结束后left>right,且left=right+1
         */

        // 如果想在找不到 target 的时候返回 -1，那么检查一下 nums[left] 和 target 是否相等即可
        // 判断 target 是否存在于 nums 中
        // 如果越界，target 肯定不存在，返回 -1
        if (left < 0 || left >= nums.length) {
            return -1;
        }
        // 判断一下 nums[left] 是不是 target
        return nums[left] == target ? left : -1;

    }

    // 寻找右侧边界的二分搜索
    public static int right_bound(int[] nums, int target) {
        if (target < nums[0] || target > nums[nums.length - 1]) {
            return -1;
        }
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                // 这里改成收缩左侧边界即可
                left = mid + 1;
            } else if (target < nums[mid]) {
                // 搜索区间变为 [left, mid-1]
                right = mid - 1;
            } else if (target > nums[mid]) {
                left = mid + 1;
            }
        }
//        return right;
        /*
        直接return right。和前面讲的 left_bound 相反：如果 target 不存在，搜索右侧边界的二分搜索返回的索引是小于 target 的最大索引。
        简单举个例子就能得到这个结论了。比如 nums = [2,3,5,7], target = 4，right_bound 函数返回值是 1，因为元素 3 是小于 4 的最大元素。
        为什么呢？因为当最后一次循环时，left=right,然后有两个分支是left = mid + 1;一个分支是right = mid - 1;
        那么必然最后一次结束后left>right,且left=right+1
         */

        // 如果想在找不到 target 的时候返回 -1，那么检查一下 nums[right] 和 target 是否相等即可
        // 判断 target 是否存在于 nums 中
        // 如果越界，target 肯定不存在，返回 -1
        if (right < 0 || right >= nums.length) {
            return -1;
        }
        // 判断一下 nums[right] 是不是 target
        return nums[right] == target ? right : -1;
    }

    public static void main(String[] args) {
        System.out.println(right_bound(new int[]{0,2,2,2,5}, 2));
    }
}
